
#ifndef RAIS_LINKEDLIST_H
#define RAIS_LINKEDLIST_H

/*	
	Rais_LinkedList: 链表结构库.
	
	Created: 2020.6.25
	Author: Raiscies.
	
	
	namespace: rais
	using type: 
		len_t = unsigned int
		idx_t = long	
	
	class:	LinkedList<T>
	public methods:
				LinkedList<URTs...>(URTs&&... items)
		len_t	getLength()
		bool 	add<URT, URTs...>(idx_t index, URT&& item, URTs&& items)
		bool	push<URT, URTs...>(URT&& item, URTs&&... items)
		bool	unshift<URTs...>(URTs&&... items)
		T&		get(idx_t index)
		T&		free(idx_t index)
		T&		shift()
		T&		pop()
		bool	del(idx_t index)
		void	clear()
		void	reverse()
		bool	swap(idx_t i1, idx_t i2)
		void 	for_each<F, ARGs...>(F f, ARGs&&... args)
		T&		operator[](idx_t index)

*/


//TODO: list reverse.



namespace rais{

using len_t = unsigned int;	//length's type
using idx_t = long; 		// index's type

class ListNode{
	public:
	ListNode* next = nullptr;
	void* item = nullptr;
	
	ListNode(void* item_p){
		this->item = item_p;
	}
};

template <typename T>
class LinkedList {
	ListNode* head = nullptr;
	len_t length = 0;
	
	public:
	
	template <typename... URTs>
	LinkedList(URTs&&... items){
		push(items...);
	}
	~LinkedList(){
		clear();
	}

	
	len_t getLength() const{return length;}
	
	template <typename URT, typename... URTs>
	bool add(idx_t index, URT&& item, URTs&&... items){
		if(index >= length) return push(item, items...);
		ListNode* newNode = new ListNode(new T(item));
		if(newNode == NULL) return false;
		
		if(length == 0) head = newNode;
		else {
			validlize(index);
			if(index == 0){
				newNode->next = head;
				head = newNode;
			}else {
				ListNode* forwardNode = getNode(index - 1);
				newNode->next = forwardNode->next;
				forwardNode->next = newNode;
			}
			
		}
		length++;
		return add(index + 1, items...);
	}
	
	//push a item to the list tail
	template <typename URT, typename... URTs>
	bool push(URT&& item, URTs&&... items){
		ListNode* newNode = new ListNode(new T(item));	//for every data, there will save its copy.
		if(newNode == NULL) return false;				//(I'm not sure this would be useful...) Fail to create a node - out of memory
		
		if(length == 0)	head = newNode;
		else 			getNode(length - 1)->next = newNode;
		
		length++;
		return push(items...);
	}
	
	template <typename... URTs>
	bool unshift(URTs&&... items){return add(0, items...);}

	
	T& get(idx_t index){
		if(length == 0) return *static_cast<T*>(nullptr);
		validlize(index);
		return *static_cast<T*>(getNode(index)->item);
	}
	
	T& free(idx_t index){
		if(length == 1) return shift();
		if(length == 0) return *static_cast<T*>(nullptr);
		validlize(index);
		
		ListNode* forwardNode = getNode(index - 1);
		ListNode* afterNode = forwardNode->next->next;
		T* retItem = static_cast<T*>(forwardNode->next->item);
		delete forwardNode->next;
		forwardNode->next = afterNode;
		length--;
		return *retItem;
	}
	
	//shift a item in the list head
	T& shift(){
		if(length == 0) return *static_cast<T*>(nullptr);
		length--;
		ListNode* target = head;
		T* retItem = static_cast<T*>(head->item);
		head = head->next;
		delete target;
		return *retItem;
	}
	
	//pop the item in the list tail
	T& pop(){
		if(length == 0) return *static_cast<T*>(nullptr);
		if(length == 1) {
			T* retItem = static_cast<T*>(head->item);
			delete head;
			head = nullptr;
			length--;
			return *retItem;
		}
		ListNode* forwardNode = getNode(length - 2);
		T* retItem = static_cast<T*>(forwardNode->next->item);
		delete forwardNode->next;
		forwardNode->next = nullptr;
		length--;
		return *retItem;
	}
	
	bool del(idx_t index){
		if(length == 0) return false;
		if(index < 0) index += static_cast<long>(length);
		if(index < 0 || index >= length) return false;
		
		if(index == 0){
			ListNode* newHead = head->next;
			delete static_cast<T*>(head->item);
			delete head;
			head = newHead;
		}else {
			ListNode* forwardNode = getNode(index - 1);
			ListNode* afterNode = forwardNode->next->next;
			delete static_cast<T*>(head->item);
			delete forwardNode->next;
			forwardNode->next = afterNode;
		}
		length--;
		return true;
	}
	
	void clear(){
		ListNode* pos = head;
		for(len_t i = 0; i < length; i++) {
			head = head->next;
			delete static_cast<T*>(pos->item);
			delete pos;
			pos = head;
		}
		length = 0;
	}
	
	/* hasn't been finished
	void reverse(){
		if(length <= 1) return;
		ListNode* fnt = nullptr;
		ListNode* nxt = head->next;
		while(true){
			head->next = fnt;
			fnt = nxt->next;
			nxt->next = head;
			if(fnt == nullptr){					//(length-2)%3 == 1
				head = fnt;
				return;
			}else if(fnt->next == nullptr) {	//(length-2)%3 == 2
				head = fnt;
				head->next = nxt;
				return;
			}
			head = fnt->next;
			fnt->next = nxt;
			if(head->next == nullptr){			//(length-2)%3 == 0
				head->next = fnt;
				return;
			}
			nxt = head->next;
		}
	}
	*/
	
	bool swap(idx_t i1, idx_t i2){
		if(length <= 1 || i1 == i2) return false;
		if(i1 < 0) i1 += static_cast<long>(length);
		if(i2 < 0) i2 += static_cast<long>(length);	
		if(i1 < 0 || i1 >= length || i2 < 0 || i2 >= length) return false;
		ListNode* node1 = getNode(i1);
		ListNode* node2 = getNode(i2);
		T* tmp = static_cast<T*>(node1->item);
		node1->item = node2->item;
		node2->item = tmp;
		return true;
	}
	
	template <typename F, typename... ARGs>
	void for_each(F f, ARGs&&... args){
		ListNode* pos = head;
		for(len_t i = 0; i < length; ++i, pos = pos->next) f(*static_cast<T*>(pos->item), args...); 
	}
	
	T& operator[](idx_t index){
		return get(index);
	}
	
	private:
	void validlize(idx_t& idx){
		//length shouldn't be zero!
		
		if(idx < 0) {
			idx += static_cast<long>(length);
			if(idx < 0) idx = 0;
		}else if(idx >= length) idx = static_cast<long>(length) - 1;
	}
	
	ListNode* getNode(len_t index) const{
		// if(index >= length) return nullptr;			//Not necessary, it's caller's duty.
		ListNode* pos = head;
		for(len_t i = 0; i < index; ++i) pos = pos->next; 
		return pos;
	}
	
	//recursion ends:
	bool push() const{return true;}	
	bool add(idx_t index) const{static_cast<void>(index)/*avoid unused warning*/; return true;}
	
	
};		//end LinkedList<T>

template <typename T>
class LinkedList<T&> {
	ListNode* head = nullptr;
	len_t length = 0;
	
	public:
	
	template <typename... RTs>
	LinkedList(RTs&... items_r){
		push(items_r...);
	}
	~LinkedList(){
		clear();
	}
	
	len_t getLength() const{return length;}
	
	template <typename... RTs>
	bool add(idx_t index, T& item_r, RTs&... items_r){
		if(index >= length) return push(item_r, items_r...);
		ListNode* newNode = new ListNode(&item_r);
		if(newNode == NULL) return false;
		
		if(length == 0) head = newNode;
		else {
			validlize(index);
			if(index == 0){
				newNode->next = head;
				head = newNode;
			}else {
				ListNode* forwardNode = getNode(index - 1);
				newNode->next = forwardNode->next;
				forwardNode->next = newNode;
			}
			
		}
		length++;
		return add(index + 1, items_r...);
		
	}

	template <typename... RTs>
	bool push(T& item_r, RTs&... items_r){
		ListNode* newNode = new ListNode(&item_r);		//for every data, there will save its pointer.
		if(newNode == NULL) return false;				//(I'm not sure if this would be useful...) Fail to create a node - out of memory
		
		if(length == 0) head = newNode;
		else 			getNode(length - 1)->next = newNode;
		
		length++;
		return push(items_r...);
	}
	
	template <typename... RTs>
	bool unshift(RTs&... items_r){return add(0, items_r...);}
	
	T& get(idx_t index){
		if(length == 0) return *static_cast<T*>(nullptr);
		validlize(index);
		return *static_cast<T*>(getNode(index)->item);
	}
	
	T& free(idx_t index){
		if(length == 1) return shift();
		if(length == 0) return *static_cast<T*>(nullptr);
		validlize(index);
		
		ListNode* forwardNode = getNode(index - 1);
		ListNode* afterNode = forwardNode->next->next;
		T* retItem = static_cast<T*>(forwardNode->next->item);
		delete forwardNode->next;
		forwardNode->next = afterNode;
		length--;
		return *retItem;
	}
	
	T& shift(){
		if(length == 0) return *static_cast<T*>(nullptr);
		length--;
		ListNode* target = head;
		T* retItem = static_cast<T*>(head->item);
		head = head->next;
		delete target;
		return *retItem;
	}
	
	T& pop(){
		if(length == 0) return *static_cast<T*>(nullptr);
		if(length == 1) {
			T* retItem = static_cast<T*>(head->item);
			delete head;
			head = nullptr;
			length--;
			return *retItem;
		}
		ListNode* forwardNode = getNode(length - 2);
		T* retItem = static_cast<T*>(forwardNode->next->item);
		delete forwardNode->next;
		forwardNode->next = nullptr;
		length--;
		return *retItem;
	}
	
	
	bool del(idx_t index){
		if(length == 0) return false;
		if(index < 0) index += static_cast<long>(length);
		if(index < 0 || index >= length) return false;
		
		if(index == 0){
			ListNode* newHead = head->next;
			delete head;
			head = newHead;
		}else {
			ListNode* forwardNode = getNode(index - 1);
			ListNode* afterNode = forwardNode->next->next;
			delete forwardNode->next;
			forwardNode->next = afterNode;
		}
		length--;
		return true;
	}
	
	void clear(){
		ListNode* pos = head;
		for(len_t i = 0; i < length; i++) {
			head = head->next;
			delete pos;
			pos = head;
		}
		length = 0;
	}
	
	bool swap(idx_t i1, idx_t i2){
		if(length <= 1 || i1 == i2) return false;
		if(i1 < 0) i1 += static_cast<long>(length);
		if(i2 < 0) i2 += static_cast<long>(length);	
		if(i1 < 0 || i1 >= length || i2 < 0 || i2 >= length) return false;
		ListNode* node1 = getNode(i1);
		ListNode* node2 = getNode(i2);
		T* tmp = static_cast<T*>(node1->item);
		node1->item = node2->item;
		node2->item = tmp;
		return true;
	}
	
	template <typename F, typename... ARGs>
	void for_each(F f, ARGs&&... args){
		ListNode* pos = head;
		for(len_t i = 0; i < length; ++i, pos = pos->next) f(*static_cast<T*>(pos->item), args...); 
	}
	
	T& operator[](idx_t index){
		return get(index);
	}
	
	
	private:
	void validlize(idx_t& idx){
		//length shouldn't be zero!
		if(idx < 0) {
			idx += static_cast<long>(length);
			if(idx < 0) idx = 0;
		}else if(idx >= length) idx = static_cast<long>(length) - 1;
	}
	
	ListNode* getNode(len_t index) const{
		ListNode* pos = head;
		for(len_t i = 0; i < index; ++i) pos = pos->next; 
		return pos;
	}
	
	bool push() const{return true;}
	bool add(idx_t index) const{static_cast<void>(index)/*avoid unused warning*/; return true;}
	
};		//end LinkedList<T&>

template <typename T>
class LinkedList<T*> {
	ListNode* head = nullptr;
	len_t length = 0;
	
	public:
	
	template <typename... PTs>
	LinkedList(PTs*... items_p){
		push(items_p...);
	}
	~LinkedList(){
		clear();
	}
	
	len_t getLength() const{return length;}
	
	template <typename... PTs>
	bool add(idx_t index, T* item_p, PTs*... items_p){
		if(index >= length) return push(item_p, items_p...);
		ListNode* newNode = new ListNode(item_p);
		if(newNode == NULL) return false;
		
		if(length == 0) head = newNode;
		else {
			validlize(index);
			if(index == 0){
				newNode->next = head;
				head = newNode;
			}else {
				ListNode* forwardNode = getNode(index - 1);
				newNode->next = forwardNode->next;
				forwardNode->next = newNode;
			}
			
		}
		length++;
		return add(index + 1, items_p...);
		
	}
	
	template <typename... PTs>
	bool push(T* item_p, PTs*... items_p){
		ListNode* newNode = new ListNode(item_p);	//for every data, there will save its copy.
		if(newNode == NULL) return false;			//(I'm not sure this would be useful...) Fail to create a node - out of memory
		
		if(length == 0) head = newNode;
		else 			getNode(length - 1)->next = newNode;
		
		length++;
		return push(items_p...);
	}
	
	template <typename... PTs>
	bool unshift(PTs*... items_p){return add(0, items_p...);}
	
	T* get(idx_t index){
		if(length == 0) return nullptr;
		validlize(index);
		return static_cast<T*>(getNode(index)->item);
	}


	T* free(idx_t index){
		if(length == 1) return shift();
		if(length == 0) return nullptr;
		validlize(index);
		
		ListNode* forwardNode = getNode(index - 1);
		ListNode* afterNode = forwardNode->next->next;
		T* retItem = static_cast<T*>(forwardNode->next->item);
		delete forwardNode->next;
		forwardNode->next = afterNode;
		length--;
		return retItem;
	}
	
	//shift a item in the list head
	T* shift(){
		if(length == 0) return nullptr;
		length--;
		ListNode* target = head;
		T* retItem = static_cast<T*>(head->item);
		head = head->next;
		delete target;
		return retItem;
	}
	
	//pop the item in the list tail
	T* pop(){
		if(length == 0) return nullptr;
		if(length == 1) {
			T* retItem = static_cast<T*>(head->item);
			delete head;
			head = nullptr;
			length--;
			return retItem;
		}
		ListNode* forwardNode = getNode(length - 2);
		T* retItem = static_cast<T*>(forwardNode->next->item);
		delete forwardNode->next;
		forwardNode->next = nullptr;
		length--;
		return retItem;
	}
	
	bool del(idx_t index){
		if(length == 0) return false;
		if(index < 0) index += static_cast<long>(length);
		if(index < 0 || index >= length) return false;
		
		if(index == 0){
			ListNode* newHead = head->next;
			delete head;
			head = newHead;
		}else {
			ListNode* forwardNode = getNode(index - 1);
			ListNode* afterNode = forwardNode->next->next;
			delete forwardNode->next;
			forwardNode->next = afterNode;
		}
		length--;
		return true;
	}
	
	void clear(){
		ListNode* pos = head;
		for(len_t i = 0; i < length; i++) {
			head = head->next;
			delete pos;
			pos = head;
		}
		length = 0;
	}
	bool swap(idx_t i1, idx_t i2){
		if(length <= 1 || i1 == i2) return false;
		if(i1 < 0) i1 += static_cast<long>(length);
		if(i2 < 0) i2 += static_cast<long>(length);	
		if(i1 < 0 || i1 >= length || i2 < 0 || i2 >= length) return false;
		ListNode* node1 = getNode(i1);
		ListNode* node2 = getNode(i2);
		T* tmp = static_cast<T*>(node1->item);
		node1->item = node2->item;
		node2->item = tmp;
		return true;
	}
	
	template <typename F, typename... ARGs>
	void for_each(F f, ARGs&&... args){
		ListNode* pos = head;
		for(len_t i = 0; i < length; ++i, pos = pos->next) f(static_cast<T*>(pos->item), args...); 
	}
	
	T* operator[](idx_t index){
		return get(index);
	}
	
	
	private:
	void validlize(idx_t& idx){
		//length shouldn't be zero!
		if(idx < 0) {
			idx += static_cast<long>(length);
			if(idx < 0) idx = 0;
		}else if(idx >= length) idx = static_cast<long>(length) - 1;
	}
	
	ListNode* getNode(len_t index) const{
		ListNode* pos = head;
		for(len_t i = 0; i < index; ++i) pos = pos->next; 
		return pos;
	}
	
	//recursion ends:
	bool push() const{return true;}	
	bool add(idx_t index) const{static_cast<void>(index)/*avoid unused warning*/; return true;}
	
};		//end LinkedList<T*>

template <>
class LinkedList<void> {
	ListNode* head = nullptr;
	len_t length = 0;
	
	public:
	
	template <typename... URTs>
	LinkedList(URTs&&... items){
		push(items...);
	}
	~LinkedList(){
		clear();
	}
	
	len_t getLength() const{return length;}
	
	template <typename RT, typename... RTs>
	bool add(idx_t index, RT& item_r, RTs&... items_r){
		if(index >= length) return push(item_r, items_r...);
		ListNode* newNode = new ListNode(&item_r);
		if(newNode == NULL) return false;
		
		if(length == 0) head = newNode;
		else {
			validlize(index);
			if(index == 0){
				newNode->next = head;
				head = newNode;
			}else {
				ListNode* forwardNode = getNode(index - 1);
				newNode->next = forwardNode->next;
				forwardNode->next = newNode;
			}
			
		}
		length++;
		return add(index + 1, items_r...);
	}
	
	//push a item to the list tail
	template <typename RT, typename... RTs>
	bool push(RT& item_r, RTs&... items_r){
		ListNode* newNode = new ListNode(&item_r);	//for every data, there will save its pointer.
		if(newNode == NULL) return false;			//(I'm not sure this would be useful...) Fail to create a node - out of memory
		
		if(length == 0) head = newNode;
		else 			getNode(length - 1)->next = newNode;
		
		length++;
		return push(items_r...);
	}
	
	template <typename... RTs>
	bool unshift(RTs&... items_r){return add(0, items_r...);}
	
	
	template <typename RET>
	RET& get(idx_t index){
		if(length == 0) return *static_cast<RET*>(nullptr);
		validlize(index);
		return *static_cast<RET*>(getNode(index)->item);
	}
	
	template <typename RET>
	RET& free(idx_t index){
		if(length == 1) return shift<RET>();
		if(length == 0) return *static_cast<RET*>(nullptr);
		validlize(index);
		
		ListNode* forwardNode = getNode(index - 1);
		ListNode* afterNode = forwardNode->next->next;
		RET* retItem = static_cast<RET*>(forwardNode->next->item);
		delete forwardNode->next;
		forwardNode->next = afterNode;
		length--;
		return *retItem;
	}
	
	//shift a item in the list head
	template <typename RET>
	RET& shift(){
		if(length == 0) return *static_cast<RET*>(nullptr);
		length--;
		ListNode* target = head;
		RET* retItem = static_cast<RET*>(head->item);
		head = head->next;
		delete target;
		return *retItem;
	}
	
	//pop the item in the list tail
	template <typename RET>
	RET& pop(){
		if(length == 0) return *static_cast<RET*>(nullptr);
		if(length == 1) {
			RET* retItem = static_cast<RET*>(head->item);
			delete head;
			head = nullptr;
			length--;
			return *retItem;
		}
		ListNode* forwardNode = getNode(length - 2);
		RET* retItem = static_cast<RET*>(forwardNode->next->item);
		delete forwardNode->next;
		forwardNode->next = nullptr;
		length--;
		return *retItem;
	}
	
	bool del(idx_t index){
		if(length == 0) return false;
		if(index < 0) index += static_cast<long>(length);
		if(index < 0 || index >= length) return false;
		
		if(index == 0){
			ListNode* newHead = head->next;
			delete head;
			head = newHead;
		}else {
			ListNode* forwardNode = getNode(index - 1);
			ListNode* afterNode = forwardNode->next->next;
			delete forwardNode->next;
			forwardNode->next = afterNode;
		}
		length--;
		return true;
	}
	
	void clear(){
		if(length == 0) return;
		ListNode* pos = head;
		for(len_t i = 0; i < length; ++i) {
			head = head->next;
			delete pos;
			pos = head;
		}
		length = 0;
	
	}
	
	bool swap(idx_t i1, idx_t i2){
		if(length <= 1 || i1 == i2) return false;
		if(i1 < 0) i1 += static_cast<long>(length);
		if(i2 < 0) i2 += static_cast<long>(length);	
		if(i1 < 0 || i1 >= length || i2 < 0 || i2 >= length) return false;
		ListNode* node1 = getNode(i1);
		ListNode* node2 = getNode(i2);
		void* tmp = node1->item;
		node1->item = node2->item;
		node2->item = tmp;
		return true;
	}
	
	template <typename... Ts, typename F, typename... ARGs>
	void for_each(F f, ARGs&&... args){
		if(length != 0) for_each_recursion<Ts...>(f, 0, head, args...);
	}
	
	
	template <typename RET>
	RET& operator[](idx_t index){
		return get<RET>(index);
	}
	
	
	private:
	void validlize(idx_t& idx){
		//length shouldn't be zero!
		
		if(idx < 0) {
			idx += static_cast<long>(length);
			if(idx < 0) idx = 0;
		}else if(idx >= length) idx = static_cast<long>(length) - 1;
	}
	
	ListNode* getNode(len_t index) const{
		// if(index >= length) return nullptr;			//Not necessary, it's caller's duty.
		ListNode* pos = head;
		for(len_t i = 0; i < index; ++i) pos = pos->next; 
		return pos;
	}
	
	template <typename T, typename... Ts, typename F, typename... ARGs>
	void for_each_recursion(F f, len_t idx, ListNode* pos, ARGs&&... args){
		f(*static_cast<T*>(pos->item), args...);
		if(idx >= length - 1) return;
		if(sizeof...(Ts) == 0){
			for(len_t i = idx; i < length; ++i, pos = pos->next) f(*static_cast<T*>(pos->item), args...);
		
		}else for_each_recursion<Ts...>(f, idx + 1, pos->next, args...);
	}

	
	//recursion ends:
	bool push() const{return true;}	
	bool add(idx_t index) const{static_cast<void>(index)/*avoid unused warning*/; return true;}
	template <typename F, typename... ARGs> void for_each_recursion(F f, len_t idx, ListNode* pos, ARGs&&... args) const{
		static_cast<void>(f);
		static_cast<void>(idx);
		static_cast<void>(pos);
	}
	
};		//end LinkedList<void>

template <>
class LinkedList<void*> {
	ListNode* head = nullptr;
	len_t length = 0;
	
	public:
	
	template <typename... PTs>
	LinkedList(PTs*... items_p){
		push(items_p...);
	}
	~LinkedList(){
		clear();
	}
	
	len_t getLength() const{return length;}
	
	template <typename... PTs>
	bool add(idx_t index, void* item_p, PTs*... items_p){
		if(index >= length) return push(item_p, items_p...);
		ListNode* newNode = new ListNode(item_p);
		if(newNode == NULL) return false;
		
		if(length == 0) head = newNode;
		else {
			validlize(index);
			if(index == 0){
				newNode->next = head;
				head = newNode;
			}else {
				ListNode* forwardNode = getNode(index - 1);
				newNode->next = forwardNode->next;
				forwardNode->next = newNode;
			}
			
		}
		length++;
		return add(index + 1, items_p...);
		
	}
	
	template <typename... PTs>
	bool push(void* item_p, PTs*... items_p){
		ListNode* newNode = new ListNode(item_p);	//for every data, there will save its copy.
		if(newNode == NULL) return false;			//(I'm not sure this would be useful...) Fail to create a node - out of memory
		
		if(length == 0) head = newNode;
		else 			getNode(length - 1)->next = newNode;
		
		length++;
		return push(items_p...);
	}
	
	template <typename... PTs>
	bool unshift(PTs*... items_p){return add(0, items_p...);}
	
	template <typename PT = void*>
	PT get(idx_t index){
		if(length == 0) return nullptr;
		validlize(index);
		return static_cast<PT>(getNode(index)->item);
	}

	template <typename PT = void*>
	PT free(idx_t index){
		if(length == 1) return shift();
		if(length == 0) return nullptr;
		validlize(index);
		
		ListNode* forwardNode = getNode(index - 1);
		ListNode* afterNode = forwardNode->next->next;
		PT retItem = static_cast<PT>(forwardNode->next->item);
		delete forwardNode->next;
		forwardNode->next = afterNode;
		length--;
		return retItem;
	}
	
	//shift a item in the list head
	template <typename PT = void*>
	PT shift(){
		if(length == 0) return nullptr;
		length--;
		ListNode* target = head;
		PT retItem = static_cast<PT>(head->item);
		head = head->next;
		delete target;
		return retItem;
	}
	
	//pop the item in the list tail
	template <typename PT = void*>
	PT pop(){
		if(length == 0) return nullptr;
		if(length == 1) {
			PT retItem = static_cast<PT>(head->item);
			delete head;
			head = nullptr;
			length--;
			return retItem;
		}
		ListNode* forwardNode = getNode(length - 2);
		PT retItem = static_cast<PT>(forwardNode->next->item);
		delete forwardNode->next;
		forwardNode->next = nullptr;
		length--;
		return retItem;
	}
	
	bool del(idx_t index){
		if(length == 0) return false;
		if(index < 0) index += static_cast<long>(length);
		if(index < 0 || index >= length) return false;
		
		if(index == 0){
			ListNode* newHead = head->next;
			delete head;
			head = newHead;
		}else {
			ListNode* forwardNode = getNode(index - 1);
			ListNode* afterNode = forwardNode->next->next;
			delete forwardNode->next;
			forwardNode->next = afterNode;
		}
		length--;
		return true;
	}
	
	void clear(){
		ListNode* pos = head;
		for(len_t i = 0; i < length; i++) {
			head = head->next;
			delete pos;
			pos = head;
		}
		length = 0;
	}
	bool swap(idx_t i1, idx_t i2){
		if(length <= 1 || i1 == i2) return false;
		if(i1 < 0) i1 += static_cast<long>(length);
		if(i2 < 0) i2 += static_cast<long>(length);	
		if(i1 < 0 || i1 >= length || i2 < 0 || i2 >= length) return false;
		ListNode* node1 = getNode(i1);
		ListNode* node2 = getNode(i2);
		void* tmp = node1->item;
		node1->item = node2->item;
		node2->item = tmp;
		return true;
	}
	
	template <typename F, typename... ARGs>
	void for_each(F f, ARGs&&... args){
		ListNode* pos = head;
		for(len_t i = 0; i < length; ++i, pos = pos->next) f(static_cast<void*>(pos->item), args...); 
	}
	
	template <typename PT>
	PT operator[](idx_t index){
		return get<PT>(index);
	}
	
	
	private:
	void validlize(idx_t& idx){
		//length shouldn't be zero!
		if(idx < 0) {
			idx += static_cast<long>(length);
			if(idx < 0) idx = 0;
		}else if(idx >= length) idx = static_cast<long>(length) - 1;
	}
	
	ListNode* getNode(len_t index) const{
		ListNode* pos = head;
		for(len_t i = 0; i < index; ++i) pos = pos->next; 
		return pos;
	}
	
	//recursion ends:
	bool push() const{return true;}	
	bool add(idx_t index) const{static_cast<void>(index)/*avoid unused warning*/; return true;}
};		//end LinkedList<void*>


}		//end namespace rais

#endif	//end RAIS_LINKEDLIST_H